package link.singlyLinkedList;

import java.util.function.Consumer;

/**
 * @author czt
 * @version 1.0
 * @since 2024/12/10
 *
 * 带哨兵的单项链表
 */
public class SinglyLinkedListSentinel {

    // 哨兵节点
    private Node head = new Node(666,null);

    private static class Node{
        // 节点值
        int value;

        // 下一个节点指针
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    /**
     * 给链表头部添加节点
     * @param value 节点值
     */
    public void addFirst(int value) {

        add(0,value);

    }

    /**
     * 遍历链表-while
     */
    public void loop1(Consumer<Integer> action) {
        // 指针从哨兵节点的next开始
        Node  p = head.next;

        // 当p不为空时，打印节点值
        while (p != null) {
            action.accept(p.value);
            // 并指向下一个节点
            p = p.next;
        }
    }

    /**
     * 遍历链表-for
     */
    public void loop2(Consumer<Integer> action) {
        for (Node p = head.next; p != null; p = p.next) {
            action.accept(p.value);
        }
    }

    /**
     * 获取最后一个节点
     * @return 最后一个节点
     */
    private Node findLast() {

        Node p = head;

        while (p.next != null) {
            p = p.next;
        }

        return p;
    }

    /**
     * 给链表尾部添加节点
     * @param value 节点值
     */
    public void addLast(int value) {
        // 查找最后一个节点
        Node last = findLast();

        // 使最后一个节点的next指向待插入的节点，待插入节点的下一个节点指向null
        last.next = new Node(value, null);

    }

    /**
     * 根据索引找节点
     * @param index 索引
     * @return 节点
     */
    private Node findNode(int index) {
        int i = -1;
        for (Node p = head; p != null; p = p.next, i++) {
            if (i == index) {
                // 找到则返回
                return p;
            }
        }
        // 找不到返回null
        return null;
    }

    /**
     * 根据索引查找节点值
     * @param index 索引
     * @return 节点值
     */
    public int getValue(int index) {
        // 先查找节点
        Node node = findNode(index);
        if (node == null) {
            // 找不到返回-1
            return -1;
        }
        // 找到返回实际值
        return node.value;
    }

    /**
     * 插入指定位置的节点
     * @param index 待插入索引
     * @param value 待插入节点值
     */
    public void add(int index, int value) {

        // 查找上一个待插入位置的上一个节点
        Node prev = findNode(index - 1);
        if (prev == null) {
            // 如果上一个节点不存在，则直接报错
            throw new RuntimeException("索引异常");
        }

        // 将上一个节点的next指向插入的节点，并且新节点的next指向上一个节点之前的next
        prev.next = new Node(value, prev.next);
    }

    /**
     * 删除第一个节点
     */
    public void removeFirst() {
        remove(0);
    }

    /**
     * 根据索引删除指定节点
     * @param index 索引
     */
    public void remove(int index) {

        // 查找待删除节点的上一个节点
        Node prev = findNode(index - 1);
        if (prev == null) {
            throw new RuntimeException("索引异常");
        }

        // 查找待删除节点
        Node removed = prev.next;
        if (removed == null) {
            throw new RuntimeException("索引异常");
        }

        // 使被删除接的上一个节点next指向被删除节点的next
        prev.next = removed.next;
    }
}


